package com.lcw.datastructure.tree.btree.notok;

import java.util.LinkedList;
import java.util.Queue;

public class BTree<K extends Comparable<K>, V> {

	private BTNode<K, V> mRoot = null;
	private long mSize = 0l;

	/**
	 * ????????
	 */
	public BTNode<K, V> getRootNode() {
		return mRoot;
	}

	/**
	 * ????????
	 */
	public long size() {
		return mSize;
	}

	/**
	 * ???B??
	 */
	public void clear() {
		mSize = 0l;
		mRoot = null;
	}

	/**
	 * ??????????
	 */
	private BTNode<K, V> createNode() {
		BTNode<K, V> btNode = new BTNode<>();
		btNode.mIsLeaf = true;
		btNode.mCurrentKeyNum = 0;
		return btNode;
	}

	/**
	 * @param key
	 */
	private void checkKey(K key) {
		if (key == null) {
			throw new IllegalArgumentException();
		}
	}

	/**
	 * ?????????????????
	 * 
	 * @param key
	 * @return ???????????????????????????????????????????
	 */
	public V search(K key) {

		checkKey(key);

		BTNode<K, V> currentNode = mRoot;

		// ????????????????洢key????
		while (currentNode != null) {
			int possibleIdx = binarySearch(mRoot, key);
			BTKeyValue<K, V> possibleKeyValue = currentNode.mKeys[possibleIdx];
			// ?ж??????????λ???????????????????????????????????????粻???????????????????????в???
			if (possibleIdx < currentNode.mCurrentKeyNum && key.compareTo(possibleKeyValue.mKey) == 0) {
				return possibleKeyValue.mValue;
			} else {
				currentNode = currentNode.mChildren[possibleIdx];
			}
		}
		return null;
	}

	/**
	 * ????????????????м???λ???????????????λ?????????????????ò????λ??
	 * 
	 * @param btNode
	 * @param key
	 * @return
	 */
	private int binarySearch(BTNode<K, V> btNode, K key) {
		BTKeyValue<K, V>[] keys = btNode.mKeys;
		int lo = 0;
		int hi = btNode.mCurrentKeyNum - 1;
		while (lo <= hi) {
			int mid = (hi - lo) / 2 + lo;
			int cmp = key.compareTo(keys[mid].mKey);
			if (cmp == 0) {
				return mid;
			} else if (cmp > 0) {
				lo = mid + 1;
			} else if (cmp < 0) {
				hi = mid - 1;
			}
		}
		return lo;
	}

	/**
	 * ????-??????BTree????
	 * 
	 * @param key   ?????????null
	 * @param value
	 */
	public void insert(K key, V value) {

		checkKey(key);

		if (mRoot == null) {
			mRoot = createNode();
		}
		// ?????????????-??????BTree????
		mRoot = insert(mRoot, key, value);

	}

	/**
	 * ????????
	 * 
	 * @param x     ?????????
	 * @param key
	 * @param value
	 * @return
	 */
	private BTNode<K, V> insert(BTNode<K, V> x, K key, V value) {

		// 1.?????ж?????????????????????????????
		if (x.mCurrentKeyNum == BTNode.UPPER_BOUND_KEYNUM) {
			x = split(x);
		}
		// 2.?????????????м?????????????????????????????????????
		int possibleIdx = binarySearch(x, key);
		/*
		 * ??????????????????????????????????????????????????(????????????????????????????????????????м???
		 * ??possibleIdx????????UPPER_BOUND_KEYNUM??????????)
		 */
		BTKeyValue<K, V> possibleKeyValue = x.mKeys[possibleIdx];
		/*
		 * 3.?ж??????????е??????????????????????????????????????????е?????possibleKeyValue???x.mKeys[x.
		 * mCurrentKeyNum]?null??????ж?possibleKeyValue???????????????????????
		 * ????????????滻???????????????????????(???????)
		 */
		if (possibleKeyValue != null && key.compareTo(possibleKeyValue.mKey) == 0) {
			possibleKeyValue.mValue = value;
			return x;
		}
		/*
		 * 4.???????????????????????????????????????????????????ж????????????????????????????????????????????????????
		 * ?????????????????鵽???????????????????????
		 */
		if (x.mIsLeaf) {
			// 4.1
			for (int i = x.mCurrentKeyNum; i > possibleIdx; i--) {
				x.mKeys[i] = x.mKeys[i - 1];
			}
			x.mKeys[possibleIdx] = new BTKeyValue<>(key, value);
			x.mCurrentKeyNum++;
			mSize++;
		} else {
			// 4.2
			BTNode<K, V> t = insert(x.mChildren[possibleIdx], key, value);
			/*
			 * 4.3?ж??????????е??????????1?????????????????????????????????????????У????????????????????????
			 */
			if (t.mCurrentKeyNum == 1) {
				// 4.3.1??????????е??????????????????????????????
				for (int i = x.mCurrentKeyNum; i > possibleIdx; i--) {
					x.mKeys[i] = x.mKeys[i - 1];
				}
				x.mKeys[possibleIdx] = t.mKeys[0];
				// 4.3.2??????????е??????????????????????????????
				for (int i = x.mCurrentKeyNum + 1; i > possibleIdx + 1; i--) {
					x.mChildren[i] = x.mChildren[i - 1];
				}
				x.mChildren[possibleIdx] = t.mChildren[0];
				x.mChildren[possibleIdx + 1] = t.mChildren[1];
				// 4.3.3???????????????????
				x.mCurrentKeyNum++;
			}
		}
		return x;
	}

	/**
	 * ???????x??????????????????????????????????????????????
	 * 
	 * @param x
	 * @return
	 */
	private BTNode<K, V> split(BTNode<K, V> x) {
		int mid = x.mCurrentKeyNum / 2;

		BTNode<K, V> left = new BTNode<>();
		for (int i = 0; i < mid; i++) {
			left.mKeys[i] = x.mKeys[i];
			left.mChildren[i] = x.mChildren[i];
		}
		left.mChildren[mid] = x.mChildren[mid];
		left.mIsLeaf = x.mIsLeaf;
		left.mCurrentKeyNum = mid;

		BTNode<K, V> right = new BTNode<>();
		for (int i = mid + 1; i < x.mCurrentKeyNum; i++) {
			right.mKeys[i - mid - 1] = x.mKeys[i];
			right.mChildren[i - mid - 1] = x.mChildren[i];
		}
		right.mChildren[x.mCurrentKeyNum - mid - 1] = x.mChildren[x.mCurrentKeyNum];
		right.mIsLeaf = x.mIsLeaf;
		right.mCurrentKeyNum = x.mCurrentKeyNum - mid - 1;

		BTNode<K, V> top = new BTNode<>();
		top.mCurrentKeyNum = 1;
		top.mIsLeaf = false;
		top.mKeys[0] = x.mKeys[mid];
		top.mChildren[0] = left;
		top.mChildren[1] = right;
		return top;
	}

	/**
	 * @return
	 */
	public BTKeyValue<K, V> minKey() {
		return minKey(mRoot);
	}

	/**
	 * @param x
	 * @return
	 */
	private BTKeyValue<K, V> minKey(BTNode<K, V> x) {
		if (x == null) {
			return null;
		}
		if (x.mChildren[0] != null) {
			return minKey(x.mChildren[0]);
		} else {
			return x.mKeys[0];
		}
	}

	/**
	 * @return
	 */
	public BTKeyValue<K, V> maxKey() {
		return maxKey(mRoot);
	}

	/**
	 * @param x
	 * @return
	 */
	private BTKeyValue<K, V> maxKey(BTNode<K, V> x) {
		if (x == null) {
			return null;
		}
		if (x.mChildren[x.mCurrentKeyNum] != null) {
			return maxKey(x.mChildren[x.mCurrentKeyNum]);
		} else {
			return x.mKeys[x.mCurrentKeyNum - 1];
		}
	}

	/**
	 * 
	 * @param key
	 * @return
	 */
	public V deleteKey(K key) {

		checkKey(key);

		V v = search(key);
		// ?????????key
		mRoot = deleteKey(mRoot, key);
		return v;
	}

	/**
	 * @param x
	 * @param key
	 * @return
	 */
	private BTNode<K, V> deleteKey(BTNode<K, V> x, K key) {

		// 1.?????????????????????????????λ??
		int possibleIdx = binarySearch(x, key);

		// 2.??????????????????????????
		if (x.mIsLeaf == true) {
			// 2.1????????????

			if (possibleIdx < x.mCurrentKeyNum && key.compareTo(x.mKeys[possibleIdx].mKey) == 0) {
				// 2.1.1?ж??????????possible????λ???????????????????????????possible????С????????????????????????????????
				// ???????????????????????????????????У??????κβ???

				for (int i = possibleIdx; i < x.mCurrentKeyNum - 1; i++) {
					x.mKeys[i] = x.mKeys[i + 1];
				}
				x.mKeys[x.mCurrentKeyNum - 1] = null;
				x.mCurrentKeyNum--;
				mSize--;
			}
		} else {
			// 2.2???????????
			if (possibleIdx < x.mCurrentKeyNum && key.compareTo(x.mKeys[possibleIdx].mKey) == 0) {
				// 2.2.1?ж??????????possible????λ???????????????????????????possible????С????????????????????????????????
				// ???????????possible??????????????????滻???????

				// 1?????possilbe???????????????
				BTKeyValue<K, V> keyNeedToSwim = maxKey(x.mChildren[possibleIdx]);

				// 2????1???м????????
				x = deleteKey(x, keyNeedToSwim.mKey);

				// 3????key?滻???????
				possibleIdx = binarySearch(x, key);
				x.mKeys[possibleIdx] = keyNeedToSwim;

			} else {
				// 2.2.2
				// ?????????????????possible?????????????????key

				// ??????
				BTNode<K, V> t = deleteKey(x.mChildren[possibleIdx], key);

				// ??????????????????????????????>=??????-1???????????????
				if (t.mCurrentKeyNum < BTNode.LOWER_BOUND_KEYNUM) {
					// ???????????>=??????-1

					// ?ж???????????????????????????????>??????-1???????????????????????????????????<=??????-1?????????????
					if (BTNode.hasLeftSiblingAtIndex(x, possibleIdx)) {
						if (BTNode.getLeftSiblingAtIndex(x, possibleIdx).mCurrentKeyNum > BTNode.LOWER_BOUND_KEYNUM) {
							leftRotate(x, possibleIdx);
						} else {
							leftMerge(x, possibleIdx);
						}
					} else if (BTNode.hasRightSiblingAtIndex(x, possibleIdx)) {
						if (BTNode.getRightSiblingAtIndex(x, possibleIdx).mCurrentKeyNum > BTNode.LOWER_BOUND_KEYNUM) {
							rightRotate(x, possibleIdx);
						} else {
							rightMerge(x, possibleIdx);
						}
					}

					// ?ж??????????????м??????????У?????????????
					if (x == mRoot && x.mCurrentKeyNum == 0) {
						x = x.mChildren[0];
					}
				}
			}
		}
		return x;
	}

	/**
	 * ??????????λ??possibleIdx??possibleIdx+1????????????????????????????????????????????
	 * 
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private BTNode<K, V> rightMerge(BTNode<K, V> x, int possibleIdx) {
		return leftMerge(x, possibleIdx + 1);
	}

	/**
	 * ??????????λ??possibleIdx??possibleIdx-1?????????
	 * 
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private BTNode<K, V> leftMerge(BTNode<K, V> x, int possibleIdx) {
		// ???????
		BTNode<K, V> leftNode = x.mChildren[possibleIdx - 1];
		// ???????????????????????
		BTKeyValue<K, V> topKey = x.mKeys[possibleIdx - 1];
		// ?????????????
		BTNode<K, V> possibleNode = x.mChildren[possibleIdx];
		// ??????????????????????
		leftNode.mKeys[leftNode.mCurrentKeyNum] = topKey;
		// ????????????????????????????
		for (int i = 0; i < possibleNode.mCurrentKeyNum; i++) {
			leftNode.mKeys[i + leftNode.mCurrentKeyNum + 1] = possibleNode.mKeys[i];
		}
		// ??????????????????
		for (int i = 0; i < possibleNode.mCurrentKeyNum + 1; i++) {
			leftNode.mChildren[i + leftNode.mCurrentKeyNum + 1] = possibleNode.mChildren[i];
		}
		// ??????????????????
		leftNode.mCurrentKeyNum += 1 + possibleNode.mCurrentKeyNum;
		// ????????
		for (int i = possibleIdx; i < x.mCurrentKeyNum; i++) {
			x.mKeys[i - 1] = x.mKeys[i];
		}
		x.mKeys[x.mCurrentKeyNum - 1] = null;
		for (int i = possibleIdx; i < x.mCurrentKeyNum; i++) {
			x.mChildren[i] = x.mChildren[i + 1];
		}
		x.mChildren[x.mCurrentKeyNum] = null;
		x.mCurrentKeyNum--;
//		System.out.println("leftMerge executed");
		return x;
	}

	/**
	 * ??????????????????
	 * 
	 * @param x
	 * @param possibleIdx
	 * @return
	 */
	private BTNode<K, V> rightRotate(BTNode<K, V> x, int possibleIdx) {

		// ????????????????С??????
		BTNode<K, V> rightNode = x.mChildren[possibleIdx + 1];
		BTKeyValue<K, V> rightKey = rightNode.mKeys[0];
		// ???????????С????
		BTNode<K, V> rightFirstNode = rightNode.mChildren[0];
		// ??????????λ???????
		BTKeyValue<K, V> topKey = x.mKeys[possibleIdx];
		// ????貹????????????????????λ?????????????????λ
		BTNode<K, V> possibleNode = x.mChildren[possibleIdx];
		possibleNode.mKeys[possibleNode.mCurrentKeyNum] = topKey;
		// ??????????С????????????
		possibleNode.mChildren[possibleNode.mCurrentKeyNum + 1] = rightFirstNode;
		possibleNode.mCurrentKeyNum++;

		// ????????????????λ???????????????????
		x.mKeys[possibleIdx] = rightKey;
		// ??????????????????С??????????????
		for (int i = 1; i < rightNode.mCurrentKeyNum; i++) {
			rightNode.mKeys[i - 1] = rightNode.mKeys[i];
		}
		rightNode.mKeys[rightNode.mCurrentKeyNum - 1] = null;
		for (int i = 1; i < rightNode.mCurrentKeyNum + 1; i++) {
			rightNode.mChildren[i - 1] = rightNode.mChildren[i];
		}
		rightNode.mChildren[rightNode.mCurrentKeyNum] = null;
		rightNode.mCurrentKeyNum--;
//		System.out.println("rightRotate executed");
		return x;
	}

	/**
	 * ??
	 * 
	 * @param x           ?????
	 * @param possibleIdx ?????????????????????
	 * @return
	 */
	private BTNode<K, V> leftRotate(BTNode<K, V> x, int possibleIdx) {

		// ??????????????????????
		BTNode<K, V> leftNode = x.mChildren[possibleIdx - 1];
		BTKeyValue<K, V> leftKey = leftNode.mKeys[leftNode.mCurrentKeyNum - 1];
		// ???????????????
		BTNode<K, V> leftLastNode = leftNode.mChildren[leftNode.mCurrentKeyNum];
		// ??????????λ???????
		BTKeyValue<K, V> topKey = x.mKeys[possibleIdx - 1];
		// ????貹?????????????????е?????????λ?????????????????????????????????
		BTNode<K, V> possibleNode = x.mChildren[possibleIdx];
		for (int i = possibleNode.mCurrentKeyNum; i > 0; i--) {
			possibleNode.mKeys[i] = possibleNode.mKeys[i - 1];
		}
		// ????????????
		for (int i = possibleNode.mCurrentKeyNum + 1; i > 0; i--) {
			possibleNode.mChildren[i] = possibleNode.mChildren[i - 1];
		}
		// ????????????????????????????????????????1
		possibleNode.mKeys[0] = topKey;
		possibleNode.mChildren[0] = leftLastNode;
		possibleNode.mCurrentKeyNum++;
		// ????????????????λ???????????????????
		x.mKeys[possibleIdx - 1] = leftKey;
		// ???????????????????????????????
		leftNode.mKeys[leftNode.mCurrentKeyNum - 1] = null;
		leftNode.mChildren[leftNode.mCurrentKeyNum] = null;
		leftNode.mCurrentKeyNum--;
//		System.out.println("leftRotate executed");
		return x;
	}

	public static void main(String[] args) {
		BTree<Integer, String> bt = new BTree<>();
		for (int i = 1; i <= 56; i++) {
			bt.insert(i, "");
		}
		System.out.println("insert completed");
		System.out.println("size before delete:" + bt.size());
		bt.deleteKey(27);
		bt.deleteKey(42);
		System.out.println("size after delete:" + bt.size());
		Queue<BTNode<Integer, String>> queue = new  LinkedList<>();
		//????B??
		queue.add(bt.getRootNode());
		while (!queue.isEmpty()) {
			BTNode<Integer, String> btn = queue.poll();
			for (int i = 0; i < btn.mCurrentKeyNum; i++) {
				System.out.print(btn.mKeys[i].mKey + " ");
			}
			System.out.println();
			if (!btn.mIsLeaf) {
				for (int i = 0; i <= btn.mCurrentKeyNum; i++) {
					queue.add(btn.mChildren[i]);
				}
			}
		}
	}
}

